package dp.二维数组;


import java.util.Arrays;

/**
 * * https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/
 *
 * 给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
 *
 *  * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493837&idx=1&sn=ae61f7453186defe61e44960d28d89e9&chksm=9bd416c5aca39fd3d64d2c659fbebf01e4994c23a644a0caaf1c66a637c97e27c2f266ef532a&scene=178&cur_album_id=2165181514903355392#rd
 */
public class _712_两个字符串的最小ASCII删除和 {

    public static void main(String[] args) {
        String s1 = "sea"; String s2 = "eat";
        _712_两个字符串的最小ASCII删除和 _712_两个字符串的最小ASCII删除和 = new _712_两个字符串的最小ASCII删除和();
        int result = _712_两个字符串的最小ASCII删除和.minimumDeleteSum(s1, s2);
        System.out.println(result);
    }

    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        // 备忘录值时-1 代表未曾计算
        meno = new int[m][n];
        for (int[] row : meno) {
            Arrays.fill(row, -1);
        }
        return dp(s1, 0, s2, 0);
    }

    int[][] meno;

    private int dp(String s1, int i, String s2, int j) {
        int res = 0;
        // base case
        if (i == s1.length()) {
            for (; j < s2.length(); j++) {
                res += s2.charAt(j);
            }
            return res;
        }

        if (j == s2.length()) {
            for (; i < s1.length(); i++) {
                res += s1.charAt(i);
            }
            return res;
        }

        if (meno[i][j] != -1) return meno[i][j];

        if (s1.charAt(i) == s2.charAt(j)) {
            // s1[i]he s2[j]都是在lcs中，不用删除
            meno[i][j] = dp(s1, i + 1, s2, j + 1);
        } else {
            // s1[i]和s2[j]至少有一个不在lcs中，删一个
            meno[i][j] = Math.min(
                    s1.charAt(i) + dp(s1, i + 1, s2, j),
                    s2.charAt(j) + dp(s1, i, s2, j + 1));
        }

        return meno[i][j];
    }
}
